#include <stdio.h>
#include "malloc.h"
#include "time.h"
#define MAX_DEPTH 8
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define EMPTY 0
#define NOT_EMPTY 1
int count = 1;
typedef int TElemType;
typedef int Status;
typedef struct BiTreeNode {
    TElemType data;
    struct BiTreeNode *lchild,*rchild,*parent;
}BiTreeNode,*BiTree;

typedef BiTreeNode QElemType;
typedef struct QueueNode{
    QElemType data;
    struct QueueNode *next;
}QueueNode;
typedef QueueNode *LinkQueue;

Status InitBiTree(BiTree *T);
Status CreateBiTree(BiTreeNode *TNode,int depth);
Status DestroyBiTree(BiTree *T);
Status ClearBiTree(BiTree *T);
Status BiTreeEmpty(BiTree T);
int BiTreeDepth(BiTree T);
Status Root(BiTree T);
Status Value(BiTree T,BiTreeNode e);
Status Assign(BiTree T,BiTreeNode *e,TElemType value);
BiTreeNode * Parent(BiTree T,BiTreeNode e);
BiTreeNode *LeftChild(BiTree T,BiTreeNode e);
BiTreeNode *RightChild(BiTree T,BiTreeNode e);
Status DeleteChild(BiTree *T,BiTreeNode e);
//二叉树四大遍历法
Status PreOrderTraverse(BiTree T);
Status InOrderTraverse(BiTree T);
Status PostOrderTraverse(BiTree T);
Status LevelOrderTraverse(BiTree T);
Status visit(BiTreeNode e);
//队列的一些基本操作，用于辅助层序遍历二叉树
Status initQueue(LinkQueue *Q);
Status enQueue(LinkQueue *Q,QElemType enter);
Status deQueue(LinkQueue *Q,QElemType *delete);
Status QueueEmpty(LinkQueue Q);
void opSystem(BiTree *T);

int main() {
    setbuf(stdout,NULL);
    BiTree biTree;
    srand(time(NULL));
    InitBiTree(&biTree);
    CreateBiTree(biTree,5);
//    销毁掉一部分子树，让其变成一个非完全二叉树
    DestroyBiTree(&biTree->lchild->rchild);
    DestroyBiTree(&biTree->rchild->rchild->lchild);
    opSystem(&biTree);
    return 0;
}

void opSystem(BiTree *T) {
    int operation = 0;
    TElemType data;
    clock_t start,finish;
    double total_time;
    printf("----------------------------------------------------------\n");
    printf("Please select what you want to do to the BiTree:\n");
    printf("1 :PreOrderTraverse the binary tree\n");
    printf("2 :inOrderTraverse the binary tree\n");
    printf("3 :postOrderTraverse the binary tree\n");
    printf("4 :levelOrderTraverse the binary tree\n");
    printf("5 :get the depth of the binary tree\n");
    printf("0 :reCreate the binaryTree\n");
    printf("-1 :Clear the BiTree\n");
    printf("-2:Destroy the BiTree\n");
    printf("----------------------------------------------------------\n");
    scanf("%d",&operation);
    switch (operation) {
        case 1:
            printf("preOrderTraverse result:\n");
            start = clock();
            PreOrderTraverse(*T);
            finish = clock();
            printf("\n");
            total_time = ((double)( finish - start)) / CLOCKS_PER_SEC;
            printf("preOrderTraverse has use %f s\n",total_time);
            opSystem(T);
            break;
        case 2:
            printf("inOrderTraverse result:\n");
            start = clock();
            InOrderTraverse(*T);
            finish = clock();
            printf("\n");
            total_time = ((double)( finish - start)) / CLOCKS_PER_SEC;
            printf("inOrderTraverse has use %f s\n",total_time);
            opSystem(T);
            break;
        case 3:
            printf("postOrderTraverse result:\n");
            start = clock();
            PostOrderTraverse(*T);
            finish = clock();
            printf("\n");
            total_time = ((double)( finish - start)) / CLOCKS_PER_SEC;
            printf("postOrderTraverse has use %f s\n",total_time);
            opSystem(T);
            break;
        case 4:
            printf("levelOrderTraverse result:\n");
            start = clock();
            LevelOrderTraverse(*T);
            finish = clock();
            printf("\n");
            total_time = ((double)( finish - start)) / CLOCKS_PER_SEC;
            printf("levelOrderTraverse has use %f s\n",total_time);
            opSystem(T);
            break;
        case 5:
            printf("the depth of the binary is %d\n", BiTreeDepth(*T));
            opSystem(T);
            break;
        case 0:
            printf("Please enter the depth:\n");
            int depth;
            scanf("%d",&depth);
            CreateBiTree(*T,depth);
            opSystem(T);
            break;
        case -1:
            ClearBiTree(T);
            printf("BiTree has been cleared.\n");
            opSystem(T);
            break;
        case -2:
            DestroyBiTree(T);
            printf("BiTree has been destroyed,program will exit soon.\n");
            break;
        default:
            break;
    }
}
//初始化二叉树
Status InitBiTree(BiTree *T) {
    *T = (BiTree) malloc(sizeof(BiTreeNode));
    (*T)->lchild  = NULL;
    (*T)->rchild = NULL;
    (*T)->parent = NULL;
}
//生成二叉树的节点&赋值，随机赋值or由全局变量count进行赋值，depth是二叉树的高度
Status CreateBiTree(BiTreeNode *TNode,int depth) {
    if (depth == 0) return 0;
    TNode->data = rand() % 100 + 1;
//    TNode->data = count++;
    TNode->rchild = (BiTreeNode *) malloc(sizeof(BiTreeNode));
    TNode->rchild->parent = TNode;
    TNode->lchild = (BiTreeNode *) malloc(sizeof(BiTreeNode));
    TNode->lchild->parent = TNode;
    if (depth <= 1) {
        TNode->lchild = NULL;
        TNode->rchild = NULL;
    }
    CreateBiTree(TNode->lchild,depth - 1);
    CreateBiTree(TNode->rchild,depth - 1);
    return OK;
}
//销毁二叉树
Status DestroyBiTree(BiTree *T) {
    if (T == NULL || *T == NULL) return ERROR;
    DestroyBiTree(&(*T)->lchild);
    DestroyBiTree(&(*T)->rchild);
    free((*T));
    *T = NULL;
    return OK;
}
//清空二叉树
Status ClearBiTree(BiTree *T) {
    if (T == NULL || *T == NULL)  return ERROR;
    (*T)->data = 0;
    ClearBiTree(&(*T)->lchild);
    ClearBiTree(&(*T)->rchild);
    return OK;
}
Status BiTreeEmpty(BiTree T) {
    if (T == NULL || T->rchild == NULL || T->lchild == NULL) return EMPTY;
    else return NOT_EMPTY;

}
int max(int a,int b) {
    if (a > b) return a;
    else return b;
}
int BiTreeDepth(BiTree T) {
    int depth = 1;
    if (T != NULL) return (max(BiTreeDepth(T->lchild), BiTreeDepth(T->rchild)) + depth);
    else return 0;
}

Status Root(BiTree T) {
    printf("the root node's data is %d",T->data);
}
Status Value(BiTree T,BiTreeNode e) {
    if (T == NULL) return ERROR;
    else return e.data;
}
Status Assign(BiTree T,BiTreeNode *e,TElemType value) {
    if (T == NULL) return ERROR;
    else e->data = value;
    return value;
}
BiTreeNode *Parent(BiTree T,BiTreeNode e) {
    if (T == NULL) return NULL;
    if (&e == T) return NULL;
    return e.parent;
}
BiTreeNode *LeftChild(BiTree T,BiTreeNode e) {
    if (T == NULL) return NULL;
    if (!(T->lchild)) return NULL;
    return T->lchild;
}
BiTreeNode *RightChild(BiTree T,BiTreeNode e)  {
    if (T == NULL) return NULL;
    if (!(T->rchild)) return NULL;
    return T->rchild;
}
//前序遍历
Status PreOrderTraverse(BiTree T) {
    if (T == NULL) return ERROR;
    visit(*T);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
    return OK;
}
//中序遍历
Status InOrderTraverse(BiTree T) {
    if (T == NULL) return ERROR;
    InOrderTraverse(T->lchild);
    visit(*T);
    InOrderTraverse(T->rchild);
    return OK;
}
//后序遍历
Status PostOrderTraverse(BiTree T) {
    if (T == NULL) return ERROR;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    visit(*T);
    return OK;
}
//层序遍历
Status LevelOrderTraverse(BiTree T) {
    LinkQueue Q;
    BiTreeNode p = *T;
    initQueue(&Q);
    enQueue(&Q,*T);
    while (QueueEmpty(Q)) {
        visit(Q->next->data);
        deQueue(&Q,&p);
        if (p.lchild) enQueue(&Q,*(p.lchild));
        if (p.rchild) enQueue(&Q,*(p.rchild));
    }
}
//访问节点（打印操作
Status visit(BiTreeNode e) {
    printf("%d ",e.data);
}
//初始化一个队列
Status initQueue(LinkQueue *Q) {
    (*Q) = (LinkQueue) malloc(sizeof(QueueNode));
    (*Q)->next = NULL;
    return OK;
}
//新增一个元素到队尾
Status enQueue(LinkQueue *Q,QElemType enter) {
    if ((*Q) == NULL) return ERROR;
    LinkQueue p = (LinkQueue) malloc(sizeof(QueueNode)),q = (*Q);
    p -> data = enter;
    p -> next = NULL;
    while (q -> next) {
        q = q -> next;
    }
    q -> next = p;
    return OK;
}
//队首元素出队
Status deQueue(LinkQueue *Q,QElemType *delete) {
    if ((*Q)->next == NULL) return ERROR;
    LinkQueue p = (*Q) -> next;
    *delete = p -> data;
    (*Q)->next = p -> next;
    free(p);
    return OK;
}
//判断队列是否为空
Status QueueEmpty(LinkQueue Q) {
    if (Q->next == NULL) return EMPTY;
    else return NOT_EMPTY;
}